#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
using namespace std;
//378. 字符串中的第一个唯一字符
class Solution1 {
public:
    int firstUniqChar(string s)
    {
        int hash[128] = { 0 };
        for (auto ch : s)
        {
            hash[ch] += 1;
        }

        int i = 0;
        for (i = 0; i < s.size(); i++)
        {
            if (hash[s[i]] == 1)
            {
                return i;
            }
        }
        return -1;
    }
};

//557.反转字符串中的单词|||
class Solution2 {
public:
    string reverseWords(string s)
    {
        int i = 0;
        int k = 0;
        for (i = 0; i < s.size(); i++)
        {
            if (s[i] == ' ')
            {
                reverse(s.begin() + k, s.begin() + i);
                k = i + 1;
            }
        }
        reverse(s.begin() + k, s.end());
        return s;
    }
};


//43.字符串相乘

//int func(string num1)
//{
//    auto it = num1.begin();
//    int num = 0;
//    while (it != num1.end())
//    {
//        num *= 10;
//        num += (*it - '0');
//        ++it;
//    }
//    return num;
//}

//int main()
//{
//    cout << func("123") << endl;
//
//    string s;
//   /* s.push_back(0+'0');
//    cout << s << endl;*/
//    s.push_back(0);
//    s.push_back(1);
//    s.push_back(2);
//    s.push_back(3);
//    cout << s << endl;
//    reverse(s.begin(), s.end());
//
//    for (auto& ch : s)
//    {
//        ch += '0';
//    }
//
//    cout << s << endl;
//    return 0;
//}

namespace xsc
{
    class Solution
    {
    public:
        string addStrings(string num1, string num2)
        {
            int i = num1.size() - 1;
            int j = num2.size() - 1;
            int carry = 0;
            int num = 0;
            string ret_str;

            while (i >= 0 || j >= 0)
            {
                int a = 0;
                int b = 0;
                i >= 0 ? a = num1[i--] - '0' : 0;
                j >= 0 ? b = num2[j--] - '0' : 0;
                num = a + b + carry;
                carry = num / 10;
                ret_str += num % 10 + '0';
            }

            if (carry == 1)
            {
                ret_str += '1';
            }

            reverse(ret_str.begin(), ret_str.end());
            return ret_str;
        }

        string multiply(string num1, string num2)
        {
            /*
                num1是被乘数，num2乘数，用乘数的每一位去乘被乘数的每一位
            */
            if (num1 == "0" || num2 == "0")
            {
                return "0";
            }
            string ans = "0";
            int m = num1.size();
            int n = num2.size();

            int i = 0;
            int z = 0;
            for (i = n - 1; i >= 0; i--)
            {
                string cur;
                //补0，乘数的第一位不需要补零，其余位都需要补零

                for (z = n - 1; z > i; z--)
                {
                    cur.push_back(0);
                }

                int x = num2[i] - '0';
                int carry = 0;//进位
                int j = 0;
                for (j = m - 1; j >= 0; j--)
                {
                    int y = num1[j] - '0';
                    int outcome = x * y + carry;
                    cur.push_back(outcome % 10);
                    carry = outcome / 10;
                }
                while (carry != 0)
                {
                    cur.push_back(carry % 10);
                    carry /= 10;
                }

                reverse(cur.begin(), cur.end());
                for (auto& ch : cur)
                {
                    ch += '0';
                }
                ans = addStrings(ans, cur);
            }
            return ans;
        }
    };
}

int main()
{
    xsc::Solution s;
    s.multiply("2", "3");

    return 0;
}

